In recent years, many communications systems have moved away from time-division multiplexed (TDM) systems to higher-speed, and more-flexible, packet-based systems. These packet-based systems often include elements that switch and translate packets of data between numerous different communications protocols. This processing often relies on FIFO buffers to store and forward data packets. Often a different FIFO is used to buffer data from each independent communication channel in order to prevent blockage by packets from other channels. Since many high-speed packet protocols support multiple independent data channels, the task of efficiently inserting and extracting packets into and out of these buffers can be challenging. This is because, with several FIFOs in the system, determining which FIFO to service next, and how to service it, may depend on several variables, including information on which FIFO is currently being serviced, as well as a scheduling algorithm that might depend on each of the other FIFO's status information (e.g., data available status) and the status of the service process (e.g., extracting packets).
The function of determining which FIFO to service next is typically implemented using a finite state machine (FSM)-based device referred to as a FIFO scheduler. In programmable, hardware-based solutions, such as field-programmable gate arrays (FPGAs) and the like, FIFO schedulers are implemented using FSMs that use combinatorial feedback logic. Typically, the more FIFOs that need to be scheduled and/or the more complicated the FIFO scheduling algorithm, the more complex the combinatorial feedback logic needed to implement the FSM of the FIFO scheduler. In order to keep the size and the execution time delay associated with FSM implementation and operation, respectively, at acceptable levels, either the number of FIFOs or the complexity of the FIFO scheduling algorithm is limited or both. This imposes undesirable constraints on such hardware-based solutions, often resulting in less-than-optimal implementations.